#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>

class BloomFilter {
private:
    std::vector<unsigned char> bit_array;
    int bloomfilter_size;
    int bloomfilter_hash_count;

    // 简单的哈希函数示例，使用两个不同的种子
    unsigned int hash1(unsigned int x) {
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = (x >> 16) ^ x;
        return x;
    }

    unsigned int hash2(unsigned int x) {
        x = ((x >> 16) ^ x) * 0x119de1f3;
        x = ((x >> 16) ^ x) * 0x119de1f3;
        x = (x >> 16) ^ x;
        return x;
    }

public:
    // 构造函数，初始化布隆过滤器
    BloomFilter(int size, int hash_count) : bloomfilter_size(size), bloomfilter_hash_count(hash_count) {
        bit_array.resize((size + 7) / 8, 0);
    }

    // 添加元素到布隆过滤器
    void add(unsigned int element) {
        for (int i = 0; i < bloomfilter_hash_count; i++) {
            unsigned int hash_val = (hash1(element) + i * hash2(element)) % bloomfilter_size;
            bit_array[hash_val / 8] |= (1 << (hash_val % 8));
        }
    }

    // 检查元素是否在布隆过滤器中
    bool check(unsigned int element) {
        for (int i = 0; i < bloomfilter_hash_count; i++) {
            unsigned int hash_val = (hash1(element) + i * hash2(element)) % bloomfilter_size;
            if (!(bit_array[hash_val / 8] & (1 << (hash_val % 8)))) {
                return false;  // 未找到该元素
            }
        }
        return true;  // 可能存在该元素
    }

    //从另一个布隆过滤器拷贝数据
    void copy_from(BloomFilter* other) {
        // 检查指针是否为空，避免空指针访问
        if (other == nullptr) {
            std::cerr << "Error: Attempted to copy from a null BloomFilter." << std::endl;
            exit(1);
        }
        
        // 复制other的bit_array到当前对象的bit_array
        this->bit_array.assign(other->bit_array.begin(), other->bit_array.end());
    }
};    